package com.datastructures2.netFlow;


import com.datastructures2.背包队列栈.Queue;

/**
 * 最短增广路径的FordFulkerson最大流算法
 * @author MaoLin Wang
 * @date 2020/3/323:40
 */
public class FordFulkerson {
    /**
     * 在剩余网络中是否存在从s到v的路径
     */
    private boolean[] marked;

    private FlowEdge[]edgeTo;

    /**
     * 当前最大流量
     */
    private double value;

    public FordFulkerson(FlowNetwork G,int s,int t) {
        //找出从s到t的流量网络G的最大流量配置
        while (hasAugmentingPath(G,s,t)){
            //利用所有存在的增广路径计算当前的瓶颈容量
            double bottle=Double.POSITIVE_INFINITY;
            for (int v=t;v!=s;v=edgeTo[v].other(v)){
                bottle=Math.min(bottle,edgeTo[v].residualCapacity(v));
            }
            //增大流量
            for (int v=t;v!=s;v=edgeTo[v].other(v)){
                edgeTo[v].addResidualFlowTo(v,bottle);
            }
            value+=bottle;
        }

    }

    /**
     * 在剩余网络中通过BFS查找增广路径
     * @param G
     * @param s
     * @param t
     * @return
     */
    private boolean hasAugmentingPath(FlowNetwork G,int s,int t){
        marked=new boolean[G.V()];
        edgeTo=new FlowEdge[G.V()];
        Queue<Integer>queue=new Queue<>();

        marked[s]=true;
        queue.enqueue(s);
        while (!queue.isEmpty()){
            int v=queue.dequeue();
            for (FlowEdge edge:G.adj(v)){
                int w=edge.other(v);
                if (edge.residualCapacity(w)>0 &&!marked[w]){
                    edgeTo[w]=edge;
                    marked[w]=true;
                    queue.enqueue(w);
                }
            }
        }
        return marked[t];
    }

    public  double value(){
        return value;
    }
    public boolean inCut(int v){
        return marked[v];
    }

    public static void main(String[] args) {
        FlowNetwork flowNetwork = new FlowNetwork(6);
        FlowEdge edge = new FlowEdge(0,1,2.0);
        FlowEdge edge2 = new FlowEdge(0,2,3.0);
        FlowEdge edge3 = new FlowEdge(1,4,1.0);
        FlowEdge edge4 = new FlowEdge(1,3,3.0);
        FlowEdge edge5 = new FlowEdge(2,3,1.0);
        FlowEdge edge6 = new FlowEdge(2,4,1.0);
        FlowEdge edge7 = new FlowEdge(3,5,2.0);
        FlowEdge edge8 = new FlowEdge(4,5,3.0);
        flowNetwork.addEdge(edge);
        flowNetwork.addEdge(edge2);
        flowNetwork.addEdge(edge3);
        flowNetwork.addEdge(edge4);
        flowNetwork.addEdge(edge5);
        flowNetwork.addEdge(edge6);
        flowNetwork.addEdge(edge7);
        flowNetwork.addEdge(edge8);
        FordFulkerson fordFulkerson = new FordFulkerson(flowNetwork,0,5);
        double value = fordFulkerson.value();
        System.out.printf(String.valueOf(value));
    }
}
